package top.humbleyuan.sort;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:30
 * @Des 链表排序，归并排序
 */
public class LeetCode_148 {
    public static void main(String[] args) {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(-3);
        int[] vals = {4,5,6,1,2,1,3,9,-7};
        head = LinkNode.formLink(head,vals);

        LinkNode.headToString(sort(head));
    }

    public static LinkNode sort(LinkNode head) {
        if(head.next == null)
            return head;

        LinkNode mid = getMid(head);
        //分割
        LinkNode rightHead = mid.next;
        mid.next = null;

        return merge(sort(head),sort(rightHead));
    }

    public static LinkNode getMid(LinkNode head) {

        if(head.next == null)
            return head;

        LinkNode slow = head,fast = head.next.next;
        while (fast != null) {
            if(fast.next == null)
                return slow.next;

            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static LinkNode merge(LinkNode left,LinkNode right) {
        if(left == null || right == null)
            return left == null ? right : left;

        LinkNode root = new LinkNode(-1);
        LinkNode temp = null;
        if(left.val <= right.val) {
            root.next = left;
            temp = left;
            left = left.next;
        }else {
            root.next = right;
            temp = right;
            right = right.next;
        }

        while (left != null && right != null) {
            if(left.val <= right.val) {
                temp.next = left;
                temp = left;
                left = left.next;
            } else {
                temp.next = right;
                temp = right;
                right = right.next;
            }
        }

        if(left != null) {
            temp.next = left;
        }else {
            temp.next = right;
        }

        return root.next;
    }
}
